package com.github.yangyishe;

import java.util.ArrayList;
import java.util.List;

/**
 * 994. 腐烂的橘子
 * https://leetcode.cn/problems/rotting-oranges/description/?envType=study-plan-v2&envId=top-100-liked
 *
 * 在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
 *
 * 值 0 代表空单元格；
 * 值 1 代表新鲜橘子；
 * 值 2 代表腐烂的橘子。
 * 每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
 *
 * 返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
 * 输出：4
 * 示例 2：
 *
 * 输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
 * 输出：-1
 * 解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上。
 * 示例 3：
 *
 * 输入：grid = [[0,2]]
 * 输出：0
 * 解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。
 *
 *
 * 提示：
 *
 * m == grid.length
 * n == grid[i].length
 * 1 <= m, n <= 10
 * grid[i][j] 仅为 0、1 或 2
 */
public class Problem994 {
    public static void main(String[] args) {

    }

    public static class Position{
        int row;
        int col;

        public Position(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }

    /**
     * 思路：
     * 类似回溯算法中的迷宫寻址问题，但比之还要略简单一些
     *
     *
     * @param grid
     * @return
     */
    public int orangesRotting(int[][] grid) {
        //1. 先统计出所有的腐烂橘子和新鲜橘子的坐标
        int height=grid.length;
        int width=grid[0].length;
        List<Position> rotOranges=new ArrayList<>();
        List<Position> freshOranges=new ArrayList<>();
        for(int row=0;row<height;row++){
            for(int col=0;col<width;col++){
                if(grid[row][col]==1){
                    freshOranges.add(new Position(row,col));
                }else if(grid[row][col]==2){
                    rotOranges.add(new Position(row,col));
                }
            }
        }

        //2. 开始循环遍历，对腐烂橘子进行遍历，并统计每分钟的腐蚀数和总腐蚀数
        // 如果某一分钟没有腐蚀任何新鲜橘子，则流程终止
        // 此时，如果还有新鲜橘子，则返回-1，否则返回之前的分钟数
        int minutes=0;
        int sumRot=0;
        int currentRot;
        List<Position> tempPositionList;
        while(true){
            currentRot=0;
            tempPositionList=new ArrayList<>();
            for(Position position:rotOranges){
                List<Position> newPositionList = rot(position, grid);
                currentRot+= newPositionList.size();
                tempPositionList.addAll(newPositionList);
            }
            if(currentRot==0){
                return sumRot==freshOranges.size()?minutes:-1;
            }else{
                sumRot+=currentRot;
                minutes++;
                rotOranges=tempPositionList;
            }
        }

    }

    private List<Position> rot(Position position,int[][] grid){
        int height=grid.length;
        int width=grid[0].length;

        int row = position.row;
        int col = position.col;

        List<Position> newPositionList=new ArrayList<>();
        if(row-1>=0&&grid[row-1][col]==1){
            grid[row-1][col]=2;
            newPositionList.add(new Position(row-1,col));
        }
        if(row+1<height&&grid[row+1][col]==1){
            grid[row+1][col]=2;
            newPositionList.add(new Position(row+1,col));
        }
        if(col-1>=0&&grid[row][col-1]==1){
            grid[row][col-1]=2;
            newPositionList.add(new Position(row,col-1));
        }
        if(col+1<width&&grid[row][col+1]==1){
            grid[row][col+1]=2;
            newPositionList.add(new Position(row,col+1));
        }

        return newPositionList;

    }
}
